In software development, it is often the case that source code is written in a high-level language easily understood by humans, and is converted into machine-readable object code by a compiler. When converting (compiling) source code into object code, the compiler performs various types of optimization in order to improve the execution efficiency of the object code. Optimization involves, for example, removing redundant instructions, changing the order in which instructions are executed, reducing the number of instructions by use of special instructions, parallelization using a parallel processing processor, and the like.
Source code often contains a plurality of successive comparison operations. For example, there is source code that determines whether the value of a certain variable matches any one of a plurality of comparison values, and starts a predetermined process if the value of the variable matches any one of the comparison values. In the case where such source code is simply compiled, the resulting object code is likely to contain, for each of the comparison values, a comparison instruction that compares the value of the variable with the comparison value, and a branch instruction that causes a jump to a predetermined instruction if the comparison result is true. That is, in the case where branch control is performed in accordance with the result of a plurality of comparison operations, a high load is likely to be placed on the processor. To prevent such a situation, some compilers perform optimization of comparison operations and branch control.
For example, there has been proposed a compiler that generates object code containing a small number of comparison instructions from source code describing a plurality of successive comparison operations. The proposed compiler detects, from intermediate code converted from source code, a comparison instruction #1 that compares data A and data C. Further, the compiler detects a comparison instruction #2 that compares data B to be stored in a memory area continuous with the data A, and data D to be stored in a memory area continuous with the data C. The compiler merges the detected comparison instructions #1 and #2 into one comparison instruction by expanding the range of data to be compared at one time.
There has also been proposed a compiler that generates object code which executes an instruction at the jump target of a branch instruction in advance using a parallel processing processor, and which discards the result of the advance execution if the value of a conditional expression is false. The proposed compiler calculates the probability that the value of the conditional expression is true, by performing a test run of the object code. If the probability that the value of the conditional expression is false is higher, the compiler inverts the conditional expression and switches the jump target of the branch instruction. Thus, the instruction supposed to be executed if the value of the original conditional expression is false is executed by the parallel processing processor in advance. This makes it possible to reduce the probability that the result of the advance execution is discarded.
There has also been proposed a compiler that reduces the number of branch instructions contained in object code. The proposed compiler detects a comparison instruction #1, and a branch instruction #1 that causes a jump to a predetermined instruction if the result of the comparison instruction #1 is false, from intermediate code converted from source code. The compiler also detects a comparison instruction #2, and a branch instruction #2 that causes a jump to the same instruction as that of the branch instruction #1 if the result of the comparison instruction #2 is false. The compiler replaces the branch instructions #1 and #2 with a logical instruction that calculates the logical AND of the result of the comparison instruction #1 and the result of the comparison instruction #2 and a branch instruction #3 that causes a jump to the predetermined instruction if the logical AND is false.
Further, there has been proposed a processor that determines whether to execute or invalidate an instruction located after a plurality of comparison instructions, based on a Boolean value stored in a condition flag register. When a comparison instruction #1 is input, the proposed processor stores a comparison result of the comparison instruction #1 in the condition flag register. When a comparison instruction #2 is input following the comparison instruction #1, the processor calculates the logical AND of the Boolean value registered in the condition flag register and the comparison result of the comparison instruction #2, and stores the logical AND in the condition flag register. After that, when an instruction other than a comparison instruction is input, the processor refers to the condition flag register, and invalidates the input instruction if the condition flag register is false. There has also been proposed a compiler that generates object code not including a branch instruction, using the functions of the above processor.
See, for example, Japanese Laid-open Patent Publications No. 02-163831, No. 2001-117890, No. 2001-265605, and No. 2004-21553.
As described above, there is source code that compares the value of a variable with each of a plurality of comparison values, and performs branch control in accordance with the comparison results. In some cases, when the result of a comparison with a certain comparison value is true, comparisons with the subsequent comparison values do not need to be performed. Thus, one method of compiler optimization for comparison operations may be to rearrange the order in which a plurality of comparison values are compared, and perform comparisons with comparison values in descending order of probability that the comparison result is true. The probability that the comparison result is true is calculated for each comparison value by executing a test run of the object code, for example.
However, there is room for improving the method of rearranging the order in which a plurality of comparison values are compared, in terms of reducing the load of the comparison process. For example, when it is likely that the value of the variable does not match any of a plurality of comparison values, comparisons might be made for all the plurality of comparison values. Thus, it is desired to reduce the average number of comparisons per value of a variable during execution.